
import operator
import random

from lib import *


def IntGenerator(num:int=500,rho:float=0.2):
    """
    不重复整数生成器
    Args:
        num: 列表大小，default 500
        rho: 随机采样率，default 0.2
    """
    memory=set()
    Rrange = int(num/rho/2+0.5)
    while num:
        num-=1
        a = random.randint(-1*Rrange,Rrange)
        while a in memory:
            a = random.randint(-1*Rrange,Rrange)
        memory.add(a)
        yield a


""" 表达式解析树 """

class EvaluateByTree(object):
    '''
    表达式解析的树算法
    '''
    def __init__(self) -> None:
        self.opers = {"+":operator.add,
                      "-":operator.sub,
                      "*":operator.mul,
                      "/":operator.truediv,
                      "%":operator.mod,
                      "!":EvaluateByTree.factorial}
    @staticmethod
    def factorial(n,t=None):
        if n == 0 :
            return 1
        else:
            return n*EvaluateByTree.factorial(n-1,None)
    
    @staticmethod
    def __analyze(expression):
        explst = list()
        tmp = ""
        for token in expression:
            if token in "1234567890.":
                tmp+=token
            elif tmp:
                explst.append(tmp)
                tmp = ""
            
            if token in "(+-*/%)":
                explst.append(token)
            elif token == "!":
                explst.extend(("!","1"))
        return explst
    
    @staticmethod
    def __buildParseTree(expression):
        ExpTree = BinaryTree(None)
        pathTree = Stack()
        pathTree.push(ExpTree)
        nowTree = ExpTree
        for token in expression:
            if token == "(":
                nowTree.insertLeft(None)
                pathTree.push(nowTree)
                nowTree = nowTree.getLeftChild()
            elif token not in "+-*/%!)": 
                nowTree.setRootVal(float(token))
                nowTree = pathTree.pop()
            elif token in "+-*/%!":
                nowTree.setRootVal(token)
                nowTree.insertRight(None)
                pathTree.push(nowTree)
                nowTree = nowTree.getRightChild()
            elif token == ")":
                nowTree = pathTree.pop()
        return ExpTree

    def evaluate(self,expression):
        expression = EvaluateByTree.__analyze(expression)
        self.ExpTree = EvaluateByTree.__buildParseTree(expression)
        return self.__evaluate(self.ExpTree)
    
    def __evaluate(self,ExpTree):
        LeftTree = ExpTree.getLeftChild()
        RightTree = ExpTree.getRightChild()

        if LeftTree and RightTree :
            func = self.opers[ExpTree.getRootVal()]
            return func(self.__evaluate(LeftTree),
                        self.__evaluate(RightTree))
        else:
            return ExpTree.getRootVal()

def printexp(tree):
    '''
    表达式树解析为字符串
    '''
    expression=""
    if tree and tree.getRootVal():
        if tree.getLeftChild():
            expression += f"({printexp(tree.getLeftChild())}"
        expression += f"{tree.getRootVal()}"
        if tree.getRightChild():
            expression += f"{printexp(tree.getRightChild())})"
    return expression


""" 二叉树排序 """

def SortByBinaryHeap(lst):
    Heap = BinHeap()
    Heap.build(lst)
    result = list()
    for _ in range(Heap.size):
        result.append(Heap.pop())
    return result


""" 改进二叉搜索树，实现非循环的中序遍历和键值更新 """

class BSTadvance(BinarySearchTree):
    def inorder(self):
        if self.size == 0:
            raise ValueError( "Empty Tree" )
        nowNode = self.root.findMin()
        result = [nowNode.key]
        while len(result) < self.size:
            nowNode = nowNode.findsuccessor()
            result.append(nowNode.key)
        return result
  
    def _put(self, key, val, nowNode):
        '''
        if key is already exist update value. 
        '''
        if key == nowNode.key:
            nowNode.value = val
        elif key < nowNode.key: # 添加左支
            if nowNode.hasLeftChild():
                self._put(key, val, nowNode.leftChild)
            else:
                nowNode.leftChild = TreeNode(key,val,parent=nowNode)
        elif key > nowNode.key: # 添加右支
            if nowNode.hasRightChild():
                self._put(key, val, nowNode.rightChild)
            else:
                nowNode.rightChild = TreeNode(key,val,parent=nowNode)


""" 线索化二叉搜索树，实现线性中序遍历（可逆序） """
def TreeNodeUpdater(cls):
    def updateTreeNode(cls, *args, **kwargs):
        self = object.__new__(cls)
        self.successor = None
        self.predecessor = None
        return self
    TreeNode.__new__ = updateTreeNode
    return cls

@TreeNodeUpdater
class ThreadedBST(BinarySearchTree):
    def __init__(self) -> None:
        self.root = None
        self.size = 0

        ThreadedBST.__start = TreeNode(None,"<start>")
        ThreadedBST.__end = TreeNode(None,"<end>")
        ThreadedBST.__start.successor = ThreadedBST.__end
        ThreadedBST.__end.predecessor = ThreadedBST.__start

    @staticmethod
    def update_pred_suc(fromNode,passNode,toNode):
        fromNode.successor = passNode
        passNode.successor = toNode
        toNode.predecessor = passNode
        passNode.predecessor = fromNode
        
    def put(self, key, value):
        '''插入數據
        調用 _put 繼續
        '''
        if self.root:
            self._put(key,value,self.root)
        else:
            self.root = TreeNode(key,value)
            ThreadedBST.update_pred_suc(ThreadedBST.__start,    # from
                                        self.root,              # pass
                                        ThreadedBST.__end)      # to
        self.size += 1

    def _put(self, key, val, nowNode):
        if key == nowNode.key:
            nowNode.value = val
        elif key < nowNode.key: 
            if nowNode.hasLeftChild():
                self._put(key, val, nowNode.leftChild)
            else:
                nowNode.leftChild = TreeNode(key,val,parent=nowNode)
                ThreadedBST.update_pred_suc(nowNode.predecessor,
                                            nowNode.leftChild,
                                            nowNode)
        elif key > nowNode.key: 
            if nowNode.hasRightChild():
                self._put(key, val, nowNode.rightChild)
            else:
                nowNode.rightChild = TreeNode(key,val,parent=nowNode)
                ThreadedBST.update_pred_suc(nowNode,
                                            nowNode.rightChild,
                                            nowNode.successor)

    def remove(self, nowNode):
        nowNode.predecessor.successor = nowNode.successor
        nowNode.successor.predecessor = nowNode.predecessor
        return super().remove(nowNode)
    
    def inorder(self, reverse = False):
        if not reverse:
            node = ThreadedBST.__start.successor
            order = [node.key]
            while isinstance(node.successor.key,(int,float)):
                order.append(node.successor.key)
                node = node.successor
            return order
        else:
            node = ThreadedBST.__end.predecessor
            order = [node.key]
            while isinstance(node.predecessor.key,(int,float)):
                order.append(node.predecessor.key)
                node = node.predecessor
            return order


""" 改进 AVL 树，实现 delete 方法 """

class AVLadvance(AVLTree):
    def _put(self, key, value, nowNode):
        if key == nowNode.key:
            nowNode.value = value
        elif key < nowNode.key:
            if nowNode.hasLeftChild():
                self._put(key,value,nowNode.leftChild)
            else:
                nowNode.leftChild = TreeNode(key,value,parent=nowNode)
                self.updateBalance_put(nowNode.leftChild)
        elif key > nowNode.key:
            if nowNode.hasRightChild():
                self._put(key,value,nowNode.rightChild)
            else:
                nowNode.rightChild = TreeNode(key,value,parent=nowNode)
                self.updateBalance_put(nowNode.rightChild)
    
    def updateBalance_put(self, node):
        return super().updateBalance(node)
    
    def updateBalance_remove(self, node):
        if node.balanceFactor > 1 or node.balanceFactor < -1:
            self.rebalance(node)
        elif node.parent != None:
            past_BF = node.parent.balanceFactor
            if node.isLeftChild():
                node.parent.balanceFactor -= 1
            elif node.isRightChild():
                node.parent.balanceFactor += 1
            if past_BF != 0:
                self.updateBalance_remove(node.parent)

    def remove(self,nowNode):
        if nowNode.hasBothChild():
            successor = nowNode.findsuccessor()
            nowNode.key = successor.key
            nowNode.value = successor.value
            nowNode = successor
        self.updateBalance_remove(nowNode)
        nowNode.spliceOut()
